/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 98152
 * Date: 2024-09-22
 * Time: 20:53
 */
public class SingleList {
    public node head;
    static class node{
        private int val;
        private node next;
        public node(int val) {
            this.val = val;
        }
    }
    //创建单链表
    public void createSingleList() {
        node A = new node(1);
        node B = new node(2);
        node C = new node(3);
        node D = new node(4);
        node E = new node(5);
        node F = new node(6);
        A.next = B;
        B.next = C;
        C.next = D;
        D.next = E;
        E.next = F;
        F.next = A;
        head = A;
    }
    //头插
    public void insertFront(int val) {
        node newNode = new node(val);
        newNode.next = head;
        head = newNode;
    }
    //尾插
    public void insertTail(int val) {
        node newNode = new node(val);
        //找尾
        if(head == null) {
            head = newNode;
            return;
        }
        node cur = head;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
    }
    //头删
    public void delFront() {
        if(head == null) {
            return;
        }
        head = head.next;
    }
    //尾删
    public void delTail() {
        if(head == null) {
            return;
        }
        //找尾
        node cur = head;
        node prev = null;
        while(cur.next != null) {
            prev = cur;
            cur = cur.next;
        }
        prev.next = null;
    }
    //查找
    public void Find(int val) {
        node cur = head;
        while(cur != null && cur.val != val) {
            cur = cur.next;
        }
        if(cur == null) {
            System.out.println("不存在");
        }else {
            System.out.println("存在");
        }
    }
    public node merge(node head1, node head2) {
        node cur1 = head1;
        node cur2 = head2;
        //创建一个带头节点
        node newNode = new node(0);
        node curN = newNode;
        while(cur1 != null && cur2 != null) {
            //较小的值尾插到新链表尾部
            if(cur1.val < cur2.val) {
                curN.next = cur1;
                cur1 = cur1.next;
            }else {
                curN.next = cur2;
                cur2 = cur2.next;
            }
            curN = curN.next;
        }
        //尾插剩余的部分
        if(cur1 == null) {
            curN.next = cur2;
        }else {
            curN.next = cur1;
        }
        return newNode.next;
    }

    //约瑟夫问题
    //需提前将这n个人建立成一个循环单向链表
    public void Joseph(int s, int m, node head) {
        node cur = head;
        for(int i = 1; i < s; i++) {
            cur = cur.next;
        }
        node curN = cur;
        while(cur != null) {
            for(int i = 1; i < m; i++) {
                cur = curN;
                curN = curN.next;
            }
            System.out.println(curN.val + "出列");
            cur.next = curN.next;
            curN = curN.next;
            cur = curN;
            if(cur.next == cur) {
                System.out.println(cur.val + "出列");
                break;
            }
        }
    }
}
